# Tokénisation <i>Byte-Pair Encoding</i>

<CourseFloatingBanner chapter={6}
  classNames="absolute z-10 right-0 top-0"
  notebooks={[
    {label: "English", value: "https://colab.research.google.com/github/huggingface/notebooks/blob/master/course/en/chapter6/section5.ipynb"},
    {label: "Français", value: "https://colab.research.google.com/github/huggingface/notebooks/blob/master/course/fr/chapter6/section5.ipynb"},
    {label: "English", value: "https://studiolab.sagemaker.aws/import/github/huggingface/notebooks/blob/master/course/en/chapter6/section5.ipynb"},
    {label: "Français", value: "https://studiolab.sagemaker.aws/import/github/huggingface/notebooks/blob/master/course/fr/chapter6/section5.ipynb"},
]} />

Le *Byte-Pair Encoding* (BPE) a été initialement développé en tant qu'algorithme de compression de textes puis utilisé par OpenAI pour la tokenisation du pré-entraînement du modèle GPT. Il est utilisé par de nombreux *transformers* dont GPT, GPT-2, RoBERTa, BART et DeBERTa.

<Youtube id="HEikzVL-lZU"/>

> [!TIP]
> 💡 Cette section couvre le BPE en profondeur, allant jusqu'à montrer une implémentation complète. Vous pouvez passer directement à la fin si vous souhaitez simplement avoir un aperçu général de l'algorithme de tokenisation.

## Algorithme d'entraînement

L'entraînement du BPE commence par le calcul de l'unique ensemble de mots utilisés dans le corpus (après les étapes de normalisation et de prétokénisation), puis la construction du vocabulaire en prenant tous les symboles utilisés pour écrire ces mots. A titre d'exemple, disons que notre corpus utilise ces cinq mots :

```
"hug", "pug", "pun", "bun", "hugs" # "câlin", "carlin", "jeu de mots", "brioche", "câlins"
```

Le vocabulaire de base sera alors `["b", "g", "h", "n", "p", "s", "u"]`. Dans le monde réel, le vocabulaire de base contient au moins tous les caractères ASCII et probablement aussi quelques caractères Unicode. Si un exemple que vous tokenisez utilise un caractère qui n'est pas dans le corpus d'entraînement, ce caractère est converti en *token* inconnu. C'est l'une des raisons pour lesquelles de nombreux modèles de NLP sont par exemple très mauvais dans l'analyse de contenus contenant des emojis.

> [!TIP]
> Les *tokenizers* du GPT-2 et de RoBERTa (qui sont assez similaires) ont une façon intelligente de gérer ce problème : ils ne considèrent pas les mots comme étant écrits avec des caractères Unicode mais avec des octets. De cette façon, le vocabulaire de base a une petite taille (256) et tous les caractères auxquels vous pouvez penser seront inclus dedans et ne finiront pas par être convertis en un *token* inconnu. Cette astuce est appelée *byte-level BPE*.

Après avoir obtenu ce vocabulaire de base, nous ajoutons de nouveaux *tokens* jusqu'à ce que la taille souhaitée du vocabulaire soit atteinte en apprenant les fusions qui sont des règles permettant de fusionner deux éléments du vocabulaire existant pour en créer un nouveau. Ainsi, au début, ces fusions créeront des *tokens* de deux caractères, puis au fur et à mesure de l'entraînement, des sous-mots plus longs.

À chaque étape de l'entraînement du *tokenizer*, l'algorithme BPE recherche la paire la plus fréquente de *tokens* existants (par « paire », nous entendons ici deux *tokens* consécutifs dans un mot). Cette paire la plus fréquente est celle qui sera fusionnée. Nous rinçons et répétons pour l'étape suivante.

Pour revenir à notre exemple précédent, supposons que les mots ont les fréquences suivantes :

```
("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)
```

ce qui veut dire que `"hug"` était présent 10 fois dans le corpus, `"pug"` 5 fois, `"pun"` 12 fois, `"bun"` 4 fois et `"hugs"`" 5 fois. Nous commençons l'entraînement en divisant chaque mot en caractères (ceux qui forment notre vocabulaire initial) afin de voir chaque mot comme une liste de *tokens* :

```
("h" "u" "g", 10), ("p" "u" "g", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "u" "g" "s", 5)
```

Ensuite, nous regardons les paires. La paire `("h", "u")` est présente dans les mots `"hug"` et `"hugs"`, donc 15 fois au total dans le corpus. Ce n'est cependant pas la paire la plus fréquente. Cet honneur revient à `("u", "g")` qui est présent dans `"hug"`, `"pug"`, et `"hugs"`, pour un total de 20 fois dans le vocabulaire.

Ainsi, la première règle de fusion apprise par le *tokenizer* est `("u", "g") -> "ug"`, ce qui signifie que `"ug"` est ajouté au vocabulaire et que la paire doit être fusionnée dans tous les mots du corpus. A la fin de cette étape, le vocabulaire et le corpus ressemblent à ceci :

```
Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "ug" "s", 5)
```

Nous avons maintenant quelques paires qui aboutissent à un *token* de plus de deux caractères. Par exemple la paire `("h", "ug")` présente 15 fois dans le corpus. La paire la plus fréquente à ce stade est `("u", "n")`, présente 16 fois dans le corpus, donc la deuxième règle de fusion apprise est `("u", "n") -> "un"`. En ajoutant cela au vocabulaire et en fusionnant toutes les occurrences existantes, nous obtenons :

```
Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("h" "ug" "s", 5)
```

Maintenant la paire la plus fréquente est `("h", "ug")` donc nous apprenons la règle de fusion `("h", "ug") -> "hug"`. Cela nous donne donc notre premier *token* de trois lettres. Après la fusion, le corpus ressemble à ceci :

```
Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un", "hug"]
Corpus: ("hug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("hug" "s", 5)
```

Et nous continuons ainsi jusqu'à ce que nous atteignions la taille de vocabulaire souhaitée.

> [!TIP]
> ✏️ **A votre tour !** A votre avis, quelle sera la prochaine règle de fusion ?

## Algorithme de tokenisation

La tokenisation suit de près le processus d'entraînement, dans le sens où les nouvelles entrées sont tokenisées en appliquant les étapes suivantes :

1. Normalisation
2. Prétokénisation
3. Découpage des mots en caractères individuels
4. Application des règles de fusion apprises dans l'ordre sur ces divisions.

Prenons l'exemple que nous avons utilisé pendant l'entraînement, avec les trois règles de fusion apprises :

```
("u", "g") -> "ug"
("u", "n") -> "un"
("h", "ug") -> "hug"
```

Le mot « bug »  sera traduit par « ["b", "ug"] ». Par contre, le mot « mug » (tasse en français) sera traduit par « ["[UNK]", "ug"] » puisque la lettre « m » ne fait pas partie du vocabulaire de base. De la même façon, le mot « thug » (voyou en français) sera tokenisé en « ["[UNK]", "hug"] » car la lettre « t » n'est pas dans le vocabulaire de base et l'application des règles de fusion résulte d'abord en la fusion de « u » et « g » et ensuite en la fusion de « hu » et « g ».

> [!TIP]
> ✏️ **A votre tour !** Comment pensez-vous que le mot « unhug » (détacher en français) sera tokenisé ?

## Implémentation du BPE

Voyons maintenant une implémentation de l'algorithme BPE. Il ne s'agira pas d'une version optimisée que vous pourrez utiliser sur un grand corpus. Nous voulons simplement vous montrer le code afin que vous puissiez comprendre un peu mieux l'algorithme.

Tout d'abord, nous avons besoin d'un corpus, alors créons un corpus simple avec quelques phrases :

```python
corpus = [
    "This is the Hugging Face Course.",
    # C'est le cours d'Hugging Face.
    "This chapter is about tokenization.",
    # Ce chapitre traite de la tokenisation.
    "This section shows several tokenizer algorithms.",
    # Cette section présente plusieurs algorithmes de tokenizer.
    "Hopefully, you will be able to understand how they are trained and generate tokens.",
    # Avec un peu de chance, vous serez en mesure de comprendre comment ils sont entraînés et génèrent des tokens.
]
```

Ensuite, nous devons prétokeniser ce corpus en mots. Puisque nous répliquons un *tokenizer* BPE (comme celui du GPT-2), nous utiliserons le *tokenizer* `gpt2` pour la prétokénisation :

```python
from transformers import AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("gpt2")
```

Ensuite, nous calculons les fréquences de chaque mot dans le corpus comme nous le faisons pour la prétokénisation :

```python
from collections import defaultdict

word_freqs = defaultdict(int)

for text in corpus:
    words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
    new_words = [word for word, offset in words_with_offsets]
    for word in new_words:
        word_freqs[word] += 1

print(word_freqs)
```

```python out
defaultdict(int, {'This': 3, 'Ġis': 2, 'Ġthe': 1, 'ĠHugging': 1, 'ĠFace': 1, 'ĠCourse': 1, '.': 4, 'Ġchapter': 1,
    'Ġabout': 1, 'Ġtokenization': 1, 'Ġsection': 1, 'Ġshows': 1, 'Ġseveral': 1, 'Ġtokenizer': 1, 'Ġalgorithms': 1,
    'Hopefully': 1, ',': 1, 'Ġyou': 1, 'Ġwill': 1, 'Ġbe': 1, 'Ġable': 1, 'Ġto': 1, 'Ġunderstand': 1, 'Ġhow': 1,
    'Ġthey': 1, 'Ġare': 1, 'Ġtrained': 1, 'Ġand': 1, 'Ġgenerate': 1, 'Ġtokens': 1})
```

L'étape suivante consiste à calculer le vocabulaire de base, formé par tous les caractères utilisés dans le corpus :

```python
alphabet = []

for word in word_freqs.keys():
    for letter in word:
        if letter not in alphabet:
            alphabet.append(letter)
alphabet.sort()

print(alphabet)
```

```python out
[ ',', '.', 'C', 'F', 'H', 'T', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'r', 's',
  't', 'u', 'v', 'w', 'y', 'z', 'Ġ']
```

Nous ajoutons également les *tokens* spéciaux utilisés par le modèle au début de ce vocabulaire. Dans le cas du GPT-2, le seul *token* spécial est `"<|endoftext|>"` :

```python
vocab = ["<|endoftext|>"] + alphabet.copy()
```

Nous devons maintenant diviser chaque mot en caractères individuels pour pouvoir commencer l'entraînement :

```python
splits = {word: [c for c in word] for word in word_freqs.keys()}
```

Maintenant que nous sommes prêts pour l'entraînement, écrivons une fonction qui calcule la fréquence de chaque paire. Nous devrons l'utiliser à chaque étape de l'entraînement :

```python
def compute_pair_freqs(splits):
    pair_freqs = defaultdict(int)
    for word, freq in word_freqs.items():
        split = splits[word]
        if len(split) == 1:
            continue
        for i in range(len(split) - 1):
            pair = (split[i], split[i + 1])
            pair_freqs[pair] += freq
    return pair_freqs
```

Jetons un coup d'œil à une partie de ce dictionnaire après les premières divisions :

```python
pair_freqs = compute_pair_freqs(splits)

for i, key in enumerate(pair_freqs.keys()):
    print(f"{key}: {pair_freqs[key]}")
    if i >= 5:
        break
```

```python out
('T', 'h'): 3
('h', 'i'): 3
('i', 's'): 5
('Ġ', 'i'): 2
('Ġ', 't'): 7
('t', 'h'): 3
```

Maintenant, trouver la paire la plus fréquente ne demande qu'une rapide boucle :

```python
best_pair = ""
max_freq = None

for pair, freq in pair_freqs.items():
    if max_freq is None or max_freq < freq:
        best_pair = pair
        max_freq = freq

print(best_pair, max_freq)
```

```python out
('Ġ', 't') 7
```

Donc la première fusion à apprendre est `('Ġ', 't') -> 'Ġt'`, et on ajoute `'Ġt'` au vocabulaire :

```python
merges = {("Ġ", "t"): "Ġt"}
vocab.append("Ġt")
```

Pour continuer, nous devons appliquer cette fusion dans notre dictionnaire `splits`. Écrivons une autre fonction pour cela :

```python
def merge_pair(a, b, splits):
    for word in word_freqs:
        split = splits[word]
        if len(split) == 1:
            continue

        i = 0
        while i < len(split) - 1:
            if split[i] == a and split[i + 1] == b:
                split = split[:i] + [a + b] + split[i + 2 :]
            else:
                i += 1
        splits[word] = split
    return splits
```

Et nous pouvons regarder le résultat de la première fusion :

```py
splits = merge_pair("Ġ", "t", splits)
print(splits["Ġtrained"])
```

```python out
['Ġt', 'r', 'a', 'i', 'n', 'e', 'd']
```

Maintenant, nous avons tout ce dont nous avons besoin pour boucler jusqu'à ce que nous ayons appris toutes les fusions que nous voulons. Visons une taille de vocabulaire de 50 :

```python
vocab_size = 50

while len(vocab) < vocab_size:
    pair_freqs = compute_pair_freqs(splits)
    best_pair = ""
    max_freq = None
    for pair, freq in pair_freqs.items():
        if max_freq is None or max_freq < freq:
            best_pair = pair
            max_freq = freq
    splits = merge_pair(*best_pair, splits)
    merges[best_pair] = best_pair[0] + best_pair[1]
    vocab.append(best_pair[0] + best_pair[1])
```

En conséquence, nous avons appris 19 règles de fusion (le vocabulaire initial avait une taille de 31 : 30 caractères dans l'alphabet plus le *token* spécial) :

```py
print(merges)
```

```python out
{('Ġ', 't'): 'Ġt', ('i', 's'): 'is', ('e', 'r'): 'er', ('Ġ', 'a'): 'Ġa', ('Ġt', 'o'): 'Ġto', ('e', 'n'): 'en',
 ('T', 'h'): 'Th', ('Th', 'is'): 'This', ('o', 'u'): 'ou', ('s', 'e'): 'se', ('Ġto', 'k'): 'Ġtok',
 ('Ġtok', 'en'): 'Ġtoken', ('n', 'd'): 'nd', ('Ġ', 'is'): 'Ġis', ('Ġt', 'h'): 'Ġth', ('Ġth', 'e'): 'Ġthe',
 ('i', 'n'): 'in', ('Ġa', 'b'): 'Ġab', ('Ġtoken', 'i'): 'Ġtokeni'}
```

Et le vocabulaire est composé du *token* spécial, de l'alphabet initial, et de tous les résultats des fusions :

```py
print(vocab)
```

```python out
['<|endoftext|>', ',', '.', 'C', 'F', 'H', 'T', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o',
 'p', 'r', 's', 't', 'u', 'v', 'w', 'y', 'z', 'Ġ', 'Ġt', 'is', 'er', 'Ġa', 'Ġto', 'en', 'Th', 'This', 'ou', 'se',
 'Ġtok', 'Ġtoken', 'nd', 'Ġis', 'Ġth', 'Ġthe', 'in', 'Ġab', 'Ġtokeni']
```

> [!TIP]
> 💡 Utiliser `train_new_from_iterator()` sur le même corpus ne donnera pas exactement le même vocabulaire. C'est parce que lorsqu'il y a un choix de la paire la plus fréquente, nous avons sélectionné la première rencontrée, alors que la bibliothèque 🤗 *Tokenizers* sélectionne la première en fonction de ses identifiants internes.

Pour tokeniser un nouveau texte, on le prétokenise, on le divise, puis on applique toutes les règles de fusion apprises :

```python
def tokenize(text):
    pre_tokenize_result = tokenizer._tokenizer.pre_tokenizer.pre_tokenize_str(text)
    pre_tokenized_text = [word for word, offset in pre_tokenize_result]
    splits = [[l for l in word] for word in pre_tokenized_text]
    for pair, merge in merges.items():
        for idx, split in enumerate(splits):
            i = 0
            while i < len(split) - 1:
                if split[i] == pair[0] and split[i + 1] == pair[1]:
                    split = split[:i] + [merge] + split[i + 2 :]
                else:
                    i += 1
            splits[idx] = split

    return sum(splits, [])
```

Nous pouvons essayer cela sur n'importe quel texte composé de caractères de l'alphabet :

```py
tokenize("This is not a token.")
```

```python out
['This', 'Ġis', 'Ġ', 'n', 'o', 't', 'Ġa', 'Ġtoken', '.']
```

> [!WARNING]
> ⚠️ Notre implémentation lancera une erreur s'il y a un caractère inconnu puisque nous n'avons rien fait pour les gérer. GPT-2 n'a pas réellement de <i>token</i> inconnu (il est impossible d'obtenir un caractère inconnu en utilisant le BPE au niveau de l'octet) mais cela pourrait arriver ici car nous n'avons pas inclus tous les octets possibles dans le vocabulaire initial. Cet aspect du BPE dépasse le cadre de cette section, nous avons donc laissé ces détails de côté.

C'est tout pour l'algorithme BPE ! Nous allons nous intéresser à WordPiece dans la suite.
